package com.zbcn.sort;

import com.alibaba.fastjson.JSON;

public class InsertSort {


    public static void main(String[] args) {
        int[] arr = {8, 7, 4, 6, 10, 9};
        //insertSort(arr);
        //bubblingSort(arr);
        selectSort(arr);
        System.out.println(JSON.toJSONString(arr));
    }


    // 选择排序
    private static void selectSort(int[] arr) {

        if (arr.length <= 1) {
            return;
        }
        // 选择排序核心思想：分为已经排序区间，未排序区间, 从未排序的当中选择最小的排到已排序的末尾
        for (int i = 0; i < arr.length; i++) {
            // 假设第一个就是最小的
            int min = i;
            // 未排序区间中选择最小的元素

            for (int j = i; j < arr.length; j++) {
                if (arr[j] <= arr[min]) {
                    min = j;
                }
            }
            // 将最小的元素放到已排序的末尾
            if (i != min) {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }

        }
    }


    /**
     * 冒泡排序
     */
    private static void bubblingSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        // 冒泡排序的核心思想：当前元素与器相邻元素比较，将最大 （最小） 元素放到最后
        for (int i = 0; i < arr.length; i++) {
            boolean noChange = true;
            // 一次冒泡：代表后面的一位 已经是最大，所以只比较 前面arr.length-i-1，如果前面的 arr.length-i-1 个元素没有比较，说明已经排好序了，没有必要再轮询
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    noChange = false;

                }
            }
            if (noChange) {
                break;
            }

        }


    }

    // 插入排序
    private static void insertSort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        // 核心思想： 将数组分为两个区间， 已排序区间 和 未排序区间。 将未排序区间的元素逐个去除，按照大小排序插入到已 排序区间
        // 未排序区间
        for (int i = 1; i < arr.length; i++) {
            int value = arr[i];
            int position = i;
            // 已排序区间,找出插入位置
            for (int j = i - 1; j >= 0; j--) {
                int targetVal = arr[j];
                if (value < targetVal) {
                    arr[j + 1] = arr[j];
                    position = j;
                } else {
                    break;

                }
            }
            arr[position] = value;
        }
    }
}
